#-*-coding:utf-8-*-
import os
import random
sys_random = random.SystemRandom()
from copy import deepcopy
import math
import numpy as np
from PIL import Image
from numpy import *
# set_printoptions(threshold=NaN)

def overseg(mat):
    # print(mat)
    occupied = np.zeros(shape=(80, 80))
    seg_mat = np.zeros(shape=(80, 80))
    pix_left = []
    for i in range(0, 80):
        for j in range(0, 80):
            pix_left.append((i, j))

    seeds = list()
    seeds_tobe_removed = list()
    overseg_regions = list()
    y = 2
    while(y<80):
        x = 2
        while(x<80):
            seeds.append([(x,y),(x+1,y),(x,y+1),(x+1,y+1)])
            x += 4
        y += 4

    row_len = int(math.sqrt(len(seeds)))
    # print("row_len = "+str(row_len))


    seeds_inValid = []

    # 移除不合理种子
    # for seed in seeds:
    #     if isValid(mat, seed) == 0:
    #         seeds.remove(seed)


    row_len = int(math.sqrt(len(seeds)))

    # 合并种子
    seeds_in_row = [[0 for col in range(row_len)] for row in range(row_len)]

    for i in range(row_len):
        for j in range(row_len):
            if isValid(mat,seeds[i * row_len + j]):
                seeds_in_row[i][j] = compute_mean(mat, seeds[i * row_len + j])
            else:
                seeds_in_row[i][j] = -2


    for i in range(row_len):
        for j in range(row_len):
            a_i = i
            while a_i > 0:
                if seeds_in_row[a_i][j] == -2 or seeds_in_row[a_i - 1][j] == -2:
                    break
                if seeds_in_row[a_i - 1][j] != -1:
                    absolute = abs(seeds_in_row[i][j] - seeds_in_row[a_i - 1][j])
                    # print("absolute: " + str(absolute))
                    if absolute < 10:
                        seeds_in_row[i][j] = -1
                        # print("seeds_in_row" + str(seeds_in_row))
                    break
                else:
                    a_i -= 1

    for i in range(row_len):
        for j in range(row_len):
            a_j = j
            while a_j > 0:
                if seeds_in_row[i][a_j] == -2 or seeds_in_row[i][a_j - 1] == -2:
                    break
                if seeds_in_row[i][a_j - 1] != -1:
                    absolute = abs(seeds_in_row[i][j] - seeds_in_row[i][a_j - 1])
                    if absolute < 10:
                        seeds_in_row[i][j] = -1
                    break
                else:
                    a_j -= 1

    # print(seeds_in_row)



    for i in range(row_len):
        for j in range(row_len):
            if seeds_in_row[i][j] == -1 or seeds_in_row[i][j] == -2:
                seeds_tobe_removed.append(seeds[i * row_len + j])
    #
    # for ivs in seeds_inValid:
    #     if alreadyExists(seeds[ivs],seeds_tobe_removed)==1:
    #         seeds_tobe_removed.append(seeds[ivs])



    # print(len(seeds_tobe_removed))


    for seed in seeds_tobe_removed:
        seeds.remove(seed)

    # for seed in seeds:
    #     if isValid(mat, seed) == 0:
    #         seeds.remove(seed)
    #     else:
    #         for cor in seed:
    #             (x, y) = cor
    #             occupied[x][y] = 1
    #             if alreadyExists(cor, pix_left) == 0:
    #                 pix_left.remove(cor)
    #         overseg_regions.append(seed)


    #确认种子
    for seed in seeds:
        for cor in seed:
            (x, y) = cor
            occupied[x][y] = 1
            if alreadyExists(cor, pix_left) == 0:
                pix_left.remove(cor)
        overseg_regions.append(seed)

    pixel_sum = 0
    former_pixel_sum = -1


    #显示种子
    seed_mat = deepcopy(mat)
    for region in overseg_regions:
        for cor in region:
            (x, y) = cor
            seed_mat[x][y] = 0
    seed_img = Image.fromarray(seed_mat)
    seed_img.show()


    # 空白图像直接返回
    if len(seeds) <= 1:
        return (False, seed_img, 0)


    former_pixel_sum = -1
    pixel_sum = 0
    while former_pixel_sum != pixel_sum:
        former_pixel_sum = pixel_sum
        pixel_sum = 0
        for region in overseg_regions:
            (overseg_regions[overseg_regions.index(region)], occupied, pix_left) = growRegion(mat, region, occupied, pix_left)
            pixel_sum += len(region)

    (overseg_regions, occupied) = allocate_pix_left(mat, overseg_regions, occupied, pix_left)


    # 灰度填充
    # for region in overseg_regions:
    #     greyValue_filled = compute_mean(mat, region)
    #     for cor in region:
    #         (x, y) = cor
    #         seg_mat[x][y] = greyValue_filled


    # seg_img = Image.fromarray(seg_mat)
    # seg_img.show()

    count = 0
    total_sum = 0

    for region in overseg_regions:
        total_sum += len(region)
        # print "region " + str(count) + ":"
        # print region
        count += 1
    # print "Total pixels: " + str(total_sum)

    boundaries = []
    boundary_list = []
    ind_b = 0
    while ind_b < len(overseg_regions):
        bry = compute_boundary(overseg_regions[ind_b])
        boundaries.append(len(bry))
        boundary_list.append(bry)
        ind_b += 1

    ori_seg_mat = deepcopy(mat)
    for boundary_in in boundary_list:
        for cor in boundary_in:
            (x, y) = cor
            ori_seg_mat[x][y] = 0
    ori_seg_img = Image.fromarray(ori_seg_mat)
    ori_seg_img.show()

    mdl = compute_mdl(mat, overseg_regions, boundaries)
    ini_mdl = mdl
    # print(overseg_regions)
    # print("MDL: " + str(mdl))
    neighborlist = neighbor_region(overseg_regions)
    # print neighborlist

    r1 = -1
    r2 = -1
    best_seg = deepcopy(overseg_regions)
    while len(best_seg) > 1:
        (mdl, r1, r2, best_seg, boundaries) = merge(mat, best_seg, neighborlist, mdl, boundaries)
        len_seg = len(best_seg)
        if r1 == -1:
            break

        neighborlist[r1].remove(r2)

        next_neighborlist = []

        for nlist in neighborlist:
            if alreadyExists(r2, nlist) == 0:
                nlist.remove(r2)
                if alreadyExists(r1, nlist) == 1:
                    nlist.append(r1)
            next_neighborlist.append(nlist)

        # for nlist in neighborlist:
        #     if alreadyExists(r2, nlist) == 0:
        #         neighborlist[neighborlist.index(nlist)].remove(r2)
        #         if alreadyExists(r1, nlist) == 1:
        #             neighborlist[neighborlist.index(nlist)].append(r1)

        next_neighborlist[r1] = list(set(neighborlist[r1] + neighborlist[r2]))

        if alreadyExists(r1, next_neighborlist[r1]) == 0:
            next_neighborlist[r1].remove(r1)
        # for r in neighborlist[r2]:
        #     if alreadyExists(r, neighborlist[r1]) == 1:
        #         neighborlist[r1].append(r)
        #     neighborlist[r1] = sorted(neighborlist[r1])

        # neighborlist.pop(r2)
        next_neighborlist.pop(r2)

        count_1 = 0
        while count_1 < len(next_neighborlist):
            count_2 = 0
            while count_2 < len(next_neighborlist[count_1]):
                if next_neighborlist[count_1][count_2] > r2:
                    next_neighborlist[count_1][count_2] = next_neighborlist[count_1][count_2] - 1
                count_2 = count_2 + 1
            count_1 = count_1 + 1

        neighborlist = deepcopy(next_neighborlist)
        # for nlist in neighborlist:
        #     for r in nlist:
        #         if r > r2:
        #             # r -= 1
        #             neighborlist[neighborlist.index(nlist)][nlist.index(r)] -= 1

        # for nlist in neighborlist:
        #     neighborlist[neighborlist.index(nlist)] = sorted(nlist)

    #     print("length: " + str(len(best_seg)))
    #     print("mdl_after: " + str(mdl) + " r1: " + str(r1) + " r2: " + str(r2))
    #     print(best_seg)
    #
    print("Best Solution:")
    # print("length: " + str(len(best_seg)))
    # print("mdl_after: " + str(mdl) + " r1: " + str(r1) + " r2: " + str(r2))
    print("mdl of best segmentation: " + str(mdl))
    # print(best_seg)

    # print(mdl/ini_mdl)

    # for region in best_seg:
    #     greyValue_filled = compute_mean(mat, region)
    #     for cor in region:
    #         (x, y) = cor
    #         seg_mat[x][y] = greyValue_filled
    # seg_img = Image.fromarray(seg_mat)

    seg_mat = deepcopy(mat)
    for region in best_seg:
        boundary = compute_boundary_in(region)
        for cor in boundary:
            (x, y) = cor
            seg_mat[x][y] = 0
    seg_img = Image.fromarray(seg_mat)
    # seg_img.show()
    print(mdl,ini_mdl)
    print(mdl/ini_mdl)

    if mdl / ini_mdl > 0.5 and mdl / ini_mdl < 0.9:
        # return (True, seg_img, mdl, boundaries, mat, best_seg)
        return (True, seg_img, mdl)
    else:
        # return (False, seg_img, mdl, boundaries, mat, best_seg)
        return (True, seg_img, mdl)

    # if mdl > 20000:
    #     return (True, seg_img)
    # else:
    #     return (False, seg_img)

def compute_mean(mat, region):
    greyValue_sum = 0
    i = 0
    for cor in region:
        (x, y) = cor
        greyValue_sum += mat[x][y]
        i += 1
        # print(mat[x][y])
    # print(greyValue_sum, i)
    greyValue_mean = greyValue_sum / i
    # print(greyValue_mean)
    return greyValue_mean

def alreadyExists(element, nlist):
    for x in nlist:
        if x == element:
            return 0
    return 1

# def isValid(mat, seed):
#     greyValue = [0, 0, 0, 0]
#     i = 0
#     for cor in seed:
#         (x, y) = cor
#         greyValue[i] = mat[x][y]
#         i += 1
#     distance = max(greyValue) - min(greyValue)
#     if distance > 10:
#         return 0
#     return 1

def isValid(mat, seed):
    max_G = -1
    min_G = 10000
    for cor in seed:
        (x, y) = cor
        greyValue = mat[x][y]
        if greyValue > max_G:
            max_G = greyValue
        if greyValue < min_G:
            min_G = greyValue
    distance = max_G - min_G
    if distance > 10:
        return 0
    return 1

def growRegion(mat, region, occupied, pix_left):
    greyValue_mean = compute_mean(mat, region)
    # print(greyValue_mean)

    boundary = compute_boundary(region)
    # print(boundary)
    for cor in boundary:
        (x, y) = cor
        # print(mat[x][y],greyValue_mean)
        if abs(int(mat[x][y]) - int(greyValue_mean)) <= 10:
            # print(mat[x][y],greyValue_mean)
            if occupied[x][y] == 0:
                region.append(cor)
                occupied[x][y] = 1
                pix_left.remove(cor)



            # print len(region)
    # print region
    # print interested
    return region, occupied, pix_left

def allocate_pix_left(mat, overseg_regions, occupied, pix_left):
    while len(pix_left) > 0:
        # print "pix_left:"
        # print pix_left
        for pix in pix_left:
            (x, y) = pix
            regions_nearby = []
            if x != 0:
                if alreadyExists((x - 1, y), pix_left) == 1:
                    for region in overseg_regions:
                        if alreadyExists((x - 1, y), region) == 0:
                            regions_nearby.append(region)
            if y != 0:
                if alreadyExists((x, y - 1), pix_left) == 1:
                    for region in overseg_regions:
                        if alreadyExists((x, y - 1), region) == 0:
                            regions_nearby.append(region)
            if x != 159:
                if alreadyExists((x + 1, y), pix_left) == 1:
                    for region in overseg_regions:
                        if alreadyExists((x + 1, y), region) == 0:
                            regions_nearby.append(region)
            if y != 159:
                if alreadyExists((x, y + 1), pix_left) == 1:
                    for region in overseg_regions:
                        if alreadyExists((x, y + 1), region) == 0:
                            regions_nearby.append(region)

            if len(regions_nearby) > 0:
                diff = 256
                for region in regions_nearby:
                    greyValue_mean = compute_mean(mat, region)
                    if abs(greyValue_mean - mat[x][y]) < diff:
                        diff = abs(greyValue_mean - mat[x][y])
                        r = region
                overseg_regions[overseg_regions.index(r)].append(pix)
                pix_left.remove(pix)
                occupied[x][y] = 1
    return overseg_regions, occupied

def compute_boundary(region):
    boundary = list()
    for cor in region:
        (x, y) = cor
        if x != 0:
            if alreadyExists((x - 1, y), region) == 1:
                boundary.append((x - 1, y))
        if y != 0:
            if alreadyExists((x, y - 1), region) == 1:
                boundary.append((x, y - 1))
        if x != 79:
            if alreadyExists((x + 1, y), region) == 1:
                boundary.append((x + 1, y))
        if y != 79:
            if alreadyExists((x, y + 1), region) == 1:
                boundary.append((x, y + 1))
    return boundary

def compute_boundary_in(region):
    boundary = list()
    for cor in region:
        (x, y) = cor
        if x != 0:
            if alreadyExists((x - 1, y), region) == 1:
                if alreadyExists((x, y), boundary) == 1:
                    boundary.append((x, y))
        if y != 0:
            if alreadyExists((x, y - 1), region) == 1:
                if alreadyExists((x, y), boundary) == 1:
                    boundary.append((x, y))
        if x != 79:
            if alreadyExists((x + 1, y), region) == 1:
                if alreadyExists((x, y), boundary) == 1:
                    boundary.append((x, y))
        if y != 79:
            if alreadyExists((x, y + 1), region) == 1:
                if alreadyExists((x, y), boundary) == 1:
                    boundary.append((x, y))
    return boundary

# def calcPerimeter(region):
#     boundary = compute_boundary(region)
#     return len(boundary)

# def calcNFCH(region):
#     boundary = compute_boundary(region)
#     pre_dir = 0
#     Directions = []
#     NFCH = 0
#     direct = [(1, 0), (1, 1), (1, -1), (0, 1), (0, -1), (-1, 1), (-1, -1), (-1, 0)]
#     dict = {(1, 0):0, (1, 1):45, (1, -1): -45, (0, 1):90, (0, -1):-90, (-1, 1):135, (-1, -1): -135, (-1, 0):180}
#     while len(boundary) > 1:
#         for i in range(0, len(boundary) - 1):
#             (x1, y1) = boundary[i]
#             for j in range(0, len(boundary) - 1):
#                 if i!= j:
#                     (x2, y2) = boundary[j]
#                     x = x2 - x1
#                     y = y2 - y1
#                     if alreadyExists((x, y), direct)==0:
#                         real_dir = dict[(x, y)]
#                         dir = real_dir - pre_dir
#                         pre_dir = real_dir
#                         Directions.append(dir)
#                         boundary.remove((x1, y1))
#         for dir in Directions:
#             if dir == 0:
#                 NFCH += 1
#             if dir == 1:
#                 NFCH += 2
#             if dir == 2:
#                 NFCH += 3
#             if dir == 3:
#                 NFCH += 4
#             if dir == 4:
#                 NFCH += 5
#             if dir == 5:
#                 NFCH += 6
#             if dir == 6:
#                 NFCH += 7
#             if dir == 7:
#                 NFCH += 7
#     return NFCH

def compute_perimeter(region):
    perimeter = 0
    for cor in region:
        (x, y) = cor
        if x == 0 or x == 79 or y == 0 or y == 79:
            perimeter += 2
        if x != 0:
            if alreadyExists((x - 1, y), region) == 1:
                perimeter += 1
        if y != 0:
            if alreadyExists((x, y - 1), region) == 1:
                perimeter += 1
        if x != 79:
            if alreadyExists((x + 1, y), region) == 1:
                perimeter += 1
        if y != 79:
            if alreadyExists((x, y + 1), region) == 1:
                perimeter += 1
    return perimeter

def compute_mdl(mat, seg, boundaries):
    area = list()
    perimeter = 0
    n = 0
    k = len(seg)
    perimeter = sum(boundaries)
    for region in seg:
        area.append(len(region))
        n += len(region)
    RSS = compute_RSS(mat, seg)
    a = 0.0
    for any in area:
        a += math.log(any)
    if RSS != 0:
        mdl = k * math.log(n) + math.log(3) * perimeter / 2 + a / 2 + n / 2 * math.log(RSS / n)
    else:
        mdl = k * math.log(n) + math.log(3) * perimeter / 2 + a / 2
    return mdl

def compute_RSS(mat, seg):
    f = np.zeros(shape=(80, 80))
    RSS = 0.0
    for region in seg:
        mean = compute_mean(mat, region)
        for cor in region:
            (x, y) = cor
            f[x][y] = mean
            RSS += (mat[x][y] - f[x][y]) * (mat[x][y] - f[x][y])
    return RSS

def neighbor_region(seg): #计算相邻区域，返回列表
    neighbor_list = list()
    for region1 in seg:
        neighbors = list()
        boundary = compute_boundary_in(region1)
        for cor in boundary:
            (x, y) = cor
            for region2 in seg:
                if alreadyExists((x+1, y), region2) == 0:
                    if alreadyExists(seg.index(region2), neighbors) == 1:
                        neighbors.append(seg.index(region2))
                elif alreadyExists((x-1, y), region2) == 0:
                    if alreadyExists(seg.index(region2), neighbors) == 1:
                        neighbors.append(seg.index(region2))
                elif alreadyExists((x, y+1), region2) == 0:
                    if alreadyExists(seg.index(region2), neighbors) == 1:
                        neighbors.append(seg.index(region2))
                elif alreadyExists((x, y-1), region2) == 0:
                    if alreadyExists(seg.index(region2), neighbors) == 1:
                        neighbors.append(seg.index(region2))
        neighbors.remove(seg.index(region1))
        neighbors_sorted = sorted(neighbors)
        neighbor_list.append(neighbors_sorted)
        # print(neighbor_list)
    return neighbor_list

def merge(mat, seg, neighbor_list, ori_mdl, boundaries):
    # print(neighbor_list)
    mdl = ori_mdl
    r1 = -1
    r2 = -1
    next_seg = deepcopy(seg)
    next_boundaries = deepcopy(boundaries)
    neighbor_list_loc = deepcopy(neighbor_list)
    for nlist in neighbor_list_loc:
        if nlist != []:
            for region_index in nlist:
                seg_loc = deepcopy(seg)
                # print (neighbor_list_loc.index(nlist), region_index)
                if alreadyExists(neighbor_list_loc.index(nlist), neighbor_list_loc[region_index]) == 0:
                    neighbor_list_loc[region_index].remove(neighbor_list_loc.index(nlist))
                #     print(neighbor_list_loc)
                # for cor_2 in seg_loc[region_index]:
                #     seg_loc[neighbor_list_loc.index(nlist)].append(cor_2)
                seg_loc[neighbor_list_loc.index(nlist)] = seg_loc[neighbor_list_loc.index(nlist)] + seg_loc[region_index]
                seg_loc[neighbor_list_loc.index(nlist)] = list(set(seg_loc[neighbor_list_loc.index(nlist)]))
                    # print(cor_2)
                    # print(alreadyExists(cor_2, seg_loc[region_index]))
                    # print(alreadyExists(cor_2, seg_loc[neighbor_list_loc.index(nlist)]))
                seg_loc.remove(seg_loc[region_index])

                boundaries_loc = deepcopy(boundaries)
                # print(region_index)
                # print(len(boundaries_loc))
                boundaries_loc[neighbor_list_loc.index(nlist)] = compute_perimeter(seg_loc[neighbor_list_loc.index(nlist)])
                boundaries_loc.pop(region_index)

                this_mdl = compute_mdl(mat, seg_loc, boundaries_loc)
                print("r1: " + str(neighbor_list_loc.index(nlist)) + " r2: " + str(region_index) + " mdl: " + str(this_mdl))
                if this_mdl < mdl:
                    mdl = this_mdl
                    r1 = neighbor_list_loc.index(nlist)
                    r2 = region_index
                    next_seg = deepcopy(seg_loc)
                    next_boundaries = deepcopy(boundaries_loc)
                    print("Best for now: r1: " + str(r1) + " r2: " + str(r2) + " mdl: " + str(mdl))
    return (mdl, r1, r2, next_seg, next_boundaries)


if __name__ =="__main__":
    # interesting_filenames = os.listdir('/Users/jerryin/Desktop/pic/')
    # interesting_images = []
    # interesting = 0
    # for name in interesting_filenames:
    #     if not name.startswith('.') and name != 'Thumbs.db':
    #         interesting_images.append(Image.open(os.path.join('/Users/jerryin/Desktop/pic/', name)))
    # for count in range(0, 10):
    #     occupied = np.zeros(shape=(80, 80))
    #     seg_mat = np.zeros(shape=(80, 80))
    #
    #     pix_left = []
    #     for i in range(0, 80):
    #         for j in range(0, 80):
    #             pix_left.append((i, j))
    #
    #     image = sys_random \
    #         .choice(interesting_images) \
    #         .resize((80, 80)) \
    #         .convert('L')
    #     image.show()
    #     mat = np.array(image)
    #     (flag, img) = overseg(mat)
    #     if flag == True:
    #         interesting += 1
    # print 'Total amount:' + str(len(interesting_images))
    # print 'Interesting amount:' + str(interesting)

    img = Image.open('/Users/jerryin/Desktop/pic/82 (3).jpg')
    img = img.resize((80, 80), Image.ANTIALIAS)
    img = img.convert("L")
    # img.show()
    mat = np.array(img)
    print(overseg(mat))